package edu.unika.aifb.graphindex.searcher.hybrid.exploration;

/**
 * Copyright (C) 2009 G�nter Ladwig (gla at aifb.uni-karlsruhe.de)
 * 
 * This file is part of the graphindex project.
 *
 * graphindex is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License, version 2
 * as published by the Free Software Foundation.
 * 
 * graphindex is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with graphindex.  If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;
import org.jgrapht.graph.DirectedMultigraph;

import edu.unika.aifb.graphindex.query.QNode;
import edu.unika.aifb.graphindex.query.QueryGraph;
import edu.unika.aifb.graphindex.query.StructuredQuery;
import edu.unika.aifb.graphindex.searcher.keyword.model.KeywordElement;
import edu.unika.aifb.graphindex.searcher.keyword.model.KeywordQNode;
import edu.unika.aifb.graphindex.searcher.keyword.model.KeywordSegment;
import edu.unika.aifb.graphindex.util.Util;

public class Subgraph extends DirectedMultigraph<NodeElement,EdgeElement> implements Comparable<Subgraph> {
	private static final long serialVersionUID = -5730502189634789126L;
	
	private Set<Cursor> m_cursors;
	private Set<EdgeElement> m_edges;
	private double m_cost;
	private Map<String,String> m_label2var;
	private boolean m_valid = true;
	private Map<String,String> m_rename;
	private Map<String,KeywordQNode> m_keywordNodes;

	public boolean track = false;
	
	private static final Logger log = Logger.getLogger(Subgraph.class);
	
	public Subgraph(Class<? extends EdgeElement> arg0) {
		super(arg0);
		m_edges = new HashSet<EdgeElement>();
		m_rename = new HashMap<String,String>();
		m_keywordNodes = new HashMap<String,KeywordQNode>();
	}

	public Subgraph(Set<Cursor> cursors) {
		this(EdgeElement.class);	
		m_cursors = cursors;
		
		Map<NodeElement,Set<String>> node2AllowedOutEdgeLabels = new HashMap<NodeElement,Set<String>>();
		Map<NodeElement,Set<String>> node2AllowedInEdgeLabels = new HashMap<NodeElement,Set<String>>();

		Set<NodeElement> keywordElementNodes = new HashSet<NodeElement>();
		
		Map<String, Set<String>> keyword2DataProperties = new HashMap<String, Set<String>>();

		for (Cursor c : cursors) {
			Cursor startCursor = c.getStartCursor();
			
			String name = m_rename.get(startCursor.getGraphElement().getLabel());
			if (name == null){
				name = startCursor.getKeywordSegments().toString();
				m_rename.put(startCursor.getGraphElement().getLabel(), name);
			}else {
				name += "," + startCursor.getKeywordSegments().toString();
				m_valid = false;
				return;
			}
			
			
			if (!m_keywordNodes.containsKey(name)) {
				KeywordQNode qnode = new KeywordQNode(name);
				if(startCursor.getGraphElement() != null && startCursor.getGraphElement() instanceof NodeElement)
					qnode.setKeywordElement(((NodeElement)startCursor.getGraphElement()).getKeywordElement());
				for (KeywordSegment ks : startCursor.getKeywordSegments()){
					for (String keyword : ks.getKeywords())
						qnode.addKeyword(keyword);
				}
				m_keywordNodes.put(name, qnode);
			}
			
			// find the first edge in the cursor chain
			Cursor cur = c.getParent();
			while (cur != null) {
				cur = cur.getParent().getParent();
			}
			
			// find the second node cursor from the beginning (which is the keyword element cursor)
			cur = c;
			NodeCursor elementCursor = null;
			while (cur != null && cur.getParent() != null) {
				if (cur instanceof NodeCursor)
					elementCursor = (NodeCursor)cur;
				else {
					elementCursor = null;
					break;
				}
				cur = cur.getParent().getParent();
			}
			
			if (elementCursor != null) {
				keywordElementNodes.add((NodeElement)elementCursor.getGraphElement());
				if (elementCursor instanceof KeywordNodeCursor){
					KeywordElement keywordElement = ((KeywordNodeCursor)elementCursor).m_keywordElement;
					for(KeywordSegment ks : c.getStartCursor().getKeywordSegments()){
						for(String keyword : ks.getKeywords()){
							Set<String> dataProperties = keyword2DataProperties.get(keyword);
							if(dataProperties != null){
								if(dataProperties.contains(keywordElement.getElementType())){
									this.m_valid = false;
									return;
								}else{
									dataProperties.add(keywordElement.getElementType());
								}
							}else{
								dataProperties = new HashSet<String>();
								dataProperties.add(keywordElement.getElementType());
								keyword2DataProperties.put(keyword, dataProperties);
							}
						}
					}
//					keywordEntities.put(elementCursor.getGraphElement().getLabel(), keywordElement.entities);
				}
			}
			
			// retrieve allowed incoming edge labels
			if (elementCursor != null && elementCursor.getInProperties().size() > 0) {
				Set<String> allowed = node2AllowedInEdgeLabels.get((NodeElement)elementCursor.getGraphElement());
				if (allowed == null) {
					allowed = new HashSet<String>(elementCursor.getInProperties());
					node2AllowedInEdgeLabels.put((NodeElement)elementCursor.getGraphElement(), allowed);
				}
				allowed.addAll(elementCursor.getInProperties());
			}

			// retrieve allowed outgoing edge labels
			if (elementCursor != null && elementCursor.getOutProperties().size() > 0) {
				Set<String> allowed = node2AllowedOutEdgeLabels.get((NodeElement)elementCursor.getGraphElement());
				if (allowed == null) {
					allowed = new HashSet<String>(elementCursor.getOutProperties());
					node2AllowedOutEdgeLabels.put((NodeElement)elementCursor.getGraphElement(), allowed);
				}
				allowed.addAll(elementCursor.getOutProperties());
			}

			for (EdgeElement e : c.getEdges()) {
				m_edges.add(e);				
				addVertex(((EdgeElement)e).getSource());
				addVertex(((EdgeElement)e).getTarget());
				addEdge(((EdgeElement)e).getSource(), ((EdgeElement)e).getTarget(), (EdgeElement)e);
			}
		}
		
		if (m_valid) {
			for (NodeElement node : node2AllowedInEdgeLabels.keySet()) {
				Set<String> allowedEdgeLabels = node2AllowedInEdgeLabels.get(node);
				for (EdgeElement edge : edgesOf(node)) {
					if (edge.getTarget().equals(node) && !allowedEdgeLabels.contains(edge.getLabel()) && !m_rename.containsKey(edge.getTarget().getLabel())) {
						m_valid = false;
						return;
					}
				}
			}
			
			for (NodeElement node : node2AllowedOutEdgeLabels.keySet()) {
				Set<String> allowedEdgeLabels = node2AllowedOutEdgeLabels.get(node);
				for (EdgeElement edge : edgesOf(node)) {
					if (edge.getSource().equals(node) && !allowedEdgeLabels.contains(edge.getLabel()) && !m_rename.containsKey(edge.getTarget().getLabel())) {
						m_valid = false;
						return;
					}
				}
			}
		}
		
		//rane
		Set<String> edgeLabels = new HashSet<String>();
		for(EdgeElement edge : m_edges){
			if(edgeLabels.contains(edge.getLabel()))
				m_valid = false;
			edgeLabels.add(edge.getLabel());
		}
		
		if(hasDanglingEdge())
			m_valid = false;
		
		double cursorCost = 0.0;
		for (Cursor c : m_cursors){
			cursorCost += c.getCost();
		}
		m_cost = cursorCost;
	}
	
	public boolean isValid() {
		return m_valid;
	}
	
	public Set<Cursor> getCursors() {
		return m_cursors;
	}
	
	
	public double getCost() {
		return m_cost;
	}

	public int compareTo(Subgraph o) {
		return ((Double)getCost()).compareTo(o.getCost());
	}
	

	public List<TranslatedQuery> attachQuery(StructuredQuery query, Map<String,Set<QNode>> ext2vars) {
		List<TranslatedQuery> queries = new ArrayList<TranslatedQuery>();
		m_label2var.putAll(m_rename);
		
		
		int x = 0;
		for (EdgeElement edge : edgeSet()) {
			String src = m_label2var.get(edge.getSource().getLabel());
			if (src == null) {
				src = "?sx" + ++x;
				m_label2var.put(edge.getSource().getLabel(), src);
			}
			
			String trg = m_label2var.get(edge.getTarget().getLabel());
			if (trg == null) {
				trg = "?sx" + ++x;
				m_label2var.put(edge.getTarget().getLabel(), trg);
			}
		}

		TranslatedQuery q = new TranslatedQuery("qt");
		for (EdgeElement edge : edgeSet()) {
			if (Util.isVariable(m_label2var.get(edge.getTarget().getLabel())))
				q.addEdge(m_label2var.get(edge.getSource().getLabel()), edge.getLabel(), m_label2var.get(edge.getTarget().getLabel()));
			else {
				QNode qnode = m_keywordNodes.get(m_label2var.get(edge.getTarget().getLabel()));
				if (qnode == null)
					qnode = new QNode(edge.getTarget().getLabel());
				q.addAttributeEdge(new QNode(m_label2var.get(edge.getSource().getLabel())), edge.getLabel(), qnode);
			}
		}

		for (QNode qn : q.getQueryGraph().vertexSet())
			if (qn.isVariable())
				q.setAsSelect(qn.getLabel());
		
		queries.add(q);
		
		return queries;
	}
	
	public QueryGraph getQueryGraph(){
		QueryGraph queryGraph = new QueryGraph();
		for (EdgeElement edge : edgeSet()) {
			NodeElement source = edge.getSource();
			NodeElement target = edge.getTarget();
			if(target.getKeywordElement() != null){
				KeywordElement keywordElement = target.getKeywordElement();
				QNode node = queryGraph.getNodeByLabel(keywordElement.getUri());
				if(node != null)
					node.setKeywordElement(keywordElement);
				else
					queryGraph.addVertex(new QNode(keywordElement));
			}else{
				queryGraph.addEdge(source.getLabel(), edge.getLabel(), target.getLabel());
			}

		}
		
		return queryGraph;
	}
	
	public String toString() {
		String edges = "";
		String addComma = "";
		for (EdgeElement edge : edgeSet()) {
			edges += addComma + edge.getLabel() + "[" + edge.getCost() + "](" + edge.getSource().getLabel() + "," + edge.getTarget().getLabel() + ")";
			addComma = ",";
		}
		return "SG[" + edgeSet().size() + "," + m_cost + "," + edges + "]";
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((m_edges == null) ? 0 : m_edges.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Subgraph other = (Subgraph)obj;
		if (m_edges == null) {
			if (other.m_edges != null)
				return false;
		} else if (!m_edges.equals(other.m_edges))
			return false;
		return true;
	}

	public boolean hasDanglingEdge() {
		if (edgeSet().size() == 1)
			return false;
		
		for (NodeElement node : vertexSet()) {
			// a node is the end of a dangling edge if
			// - if it's a "dead end", i.e. total degree is 1
			// - the node has no augmented edges (which will be attached later)
			// - the node is not the link to the structured query (if there is any)
			if (outDegreeOf(node) + inDegreeOf(node) == 1 && node.getKeywordSegment() == null && !node.getLabel().startsWith("db"))
				return true;
		}
		
		return false;
	}
}
